#include <algorithm>
#include <climits>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

class Solution {
public:
  int bt(TreeNode *root, int &maxPathSum) {
    if (root == nullptr)
      return 0;
    int left = bt(root->left, maxPathSum);
    int right = bt(root->right, maxPathSum);
    int tmp_max = root->val;
    if (left > 0) {
      tmp_max += left;
    }
    if (right > 0) {
      tmp_max += right;
    }
    maxPathSum = max(max(tmp_max, root->val), maxPathSum);
    int maxValue = max(left, right);
    if (maxValue > 0) {
      return maxValue + root->val;
    } else {
      return root->val;
    }
  }
  int maxPathSum(TreeNode *root) {
    int maxPathSum = INT_MIN;
    int v = bt(root, maxPathSum);
    return max(maxPathSum, v);
  }
};